// ============================================================================
//
// Graph framework by Aurelien Moreau aurelien.moreau@gmail.com
// Modified by Pierre CHATEL chatelp@gmail.com
// Distributed under LGPL
// Copyright (C) Aurelien Moreau, 2008, 2009. All rights reserved
//
// ============================================================================

package com.thalesgroup.graphFramework.algorithms;

import java.util.Iterator;

import com.thalesgroup.graphFramework.core.Edge;
import com.thalesgroup.graphFramework.core.Graph;
import com.thalesgroup.graphFramework.core.Vertex;


public class FordBiggestPath {

	public static <V, E> double compute(final Graph<V, E> g,
			final Vertex<V, E> s) {

		final String W = LeastPathCost.W;

		for(Iterator<Vertex<V,E>> iv=g.getVertices(); iv.hasNext();) {
			Vertex<V,E> v=iv.next();
			v.setUserFeature(W, Double.MAX_VALUE);
		}
		s.setUserFeature(W, 0.);

		boolean mod = true;
		while (mod) {
			mod = false;
			for(Iterator<Vertex<V,E>> iv=g.getVertices(); iv.hasNext();) {
				Vertex<V,E> v=iv.next();
				final Double vv = (Double) v.getUserFeature(W);
				if (vv < Double.MAX_VALUE) {
					for(Iterator<Edge<V,E>> ie=v.getOuts(); ie.hasNext();) {
						Edge<V,E> e=ie.next();
						final Double uu = (Double) e.getOut().getUserFeature(W);
						final double sum = vv + 1;
						if (uu < sum || uu == Double.MAX_VALUE) {
							e.getOut().setUserFeature(W, sum);
							mod = true;
						}
					}
				}
			}
		}

		double max = 0;
		for(Iterator<Vertex<V,E>> iv=g.getVertices(); iv.hasNext();) {
			Vertex<V,E> v=iv.next();
			final Double nValue = (Double) v.getUserFeature(W);
			if (nValue != Double.MAX_VALUE) {
				max = Math.max((Double) v.getUserFeature(W), max);
			}
		}

		return max;
	}
}
